1. Field of the Invention
The present invention relates to a finite-state machine for reliable computing and adjustment systems.
2. Description of the Related Art
Finite-state machines (FSM) are used to provide a sequence of predetermined actions in digital computing systems. Said finite-state machines (FSM) are usually composed of a combinatorial logic 1 and of a state memory 2, as illustrated in FIG. 1. The signals of the outputs 3 and the signals of the future states 4 are generated by the combinatorial logic 1 from the signals of the inputs 6 and from the signals of the current states 7, and the electronics of the combinatorial logic 1 performs the following logic operation:
if (CURRENT STATE) and (INPUTS) then (FUTURE STATE) and (OUTPUTS).
Finite-state machines can be implemented in bipolar technology, in MOS technology or in gallium arsenide (GaAs) technology, using programmable logic arrays (PLA), or nonvolatile memories (ROM), or logic gate arrays, or completely or partially dedicated cells.
Logical machines have a fundamental property, i.e. if m is the number of external input signals 6 and n is the number of the signals of the current states 7, then the complexity, i.e. the number of product terms, of the combinatorial logic 1 is equal to .sub.2 (m+n). This complexity value naturally rises exponentially as the numbers m and n become larger, even independently.
Due to the considerable number of input signals, i.e. of the external input signals 6 and of the current state signals 7, finite-state machines are seldom completely defined, or rather the number of states used is smaller than the maximum capacity of the finite-state machine itself, so that there is typically large set of undefined states.
As an unwanted result, if the finite-state machine assumes one of the undefined states, for example due to an interruption in the power supply or to noise of whatever origin, said finite-state machine has an unwanted and unknown behavior.
This last behavior is absolutely unacceptable, especially in those cases in which finite-state machines control an aircraft, an electric nuclear power plant, a telephone network or a medical instrument.
A solution currently used in order to obviate the unwanted behaviors of the finite-state machine consists in using a so-called watchdog timer, illustrated in FIG. 2, i.e. a programmable timer which, if it is not periodically reset, generates an interrupt which resets the entire system.
Said watchdog timer is composed of a counter 8 which is connected to a comparator 9. Said comparator receives in input a word 9a of n bits which represents the period of the watchdog timer, and sets a system reset signal 11. The system reset signal 11 is set on input to an OR logical gate 12, and a second input to said logical gate 12 is a reset signal 13. The OR logical gate 12 sets, toward the counter 8, a counter reset signal 14 which resets said counter either by means of the system reset signal 11, in case of a system reset, or by means of the reset signal 13.
The disadvantages of this solution are numerous and can be summarized in the need for special circuits, such as the watchdog timer, and in the need for the user program to constantly check whether the watchdog timer must be reset or not. This last disadvantage requires the use of a further timer which generates a signal 8a, either of a circuital type or of a software type, and therefore increases the cost of the development of the user program, reducing its performance, due to the need for constant checking of the watchdog timer.
There are also problems related to the operation of the watchdog timer: the finite-state machine can in fact have an abnormal behavior lasting up to one time period of the watchdog timer; in other words, if any event induces the finite-state machine to malfunction immediately after the resetting of the watchdog timer, an entire time period or machine cycle must elapse before the new setting of either a system reset signal 11 or a reset signal 13.
Finally, and more dangerously, the watchdog timer is reset by the output of a finite-state machine and does not take into account the current state of said machine. The watchdog timer can thus be reset by the finite-state machine although said machine is in an undefined state and abnormal behavior continues absolutely undisturbed.
A better solution consists in providing a known state as future state for each of the undefined states, but this solution entails up to 2.sup.n -k additional product terms, where n is the number of bits of a state and k is the number of states defined in the finite-state machine. In the case of 8 state bits (2.sup.8 = 256) and of 129 defined states, another 127 product terms are required. This last solution has the disadvantage that the finite-state machine does not interrupt its operations after an undefined state has been reached unless this has been specified beforehand in the defined state vector.